{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "y5UdBkJ6Mohb"
      },
      "source": [
        "##### Copyright 2020 Google"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "cellView": "form",
        "id": "rBLKFEKeMpq6"
      },
      "outputs": [],
      "source": [
        "#@title Licensed under the Apache License, Version 2.0 (the \"License\");\n",
        "# you may not use this file except in compliance with the License.\n",
        "# You may obtain a copy of the License at\n",
        "#\n",
        "# https://www.apache.org/licenses/LICENSE-2.0\n",
        "#\n",
        "# Unless required by applicable law or agreed to in writing, software\n",
        "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
        "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
        "# See the License for the specific language governing permissions and\n",
        "# limitations under the License."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vYA4VckiMuB6"
      },
      "source": [
        "# Routing with t|ket>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kHP0aFB1M1Ka"
      },
      "source": [
        "<table class=\"tfo-notebook-buttons\" align=\"left\">\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://www.example.org/cirq/experiments/qaoa/routing_with_tket\"><img src=\"https://www.tensorflow.org/images/tf_logo_32px.png\" />View on QuantumLib</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://colab.research.google.com/github/quantumlib/ReCirq/blob/master/docs/qaoa/routing_with_tket.ipynb\"><img src=\"https://www.tensorflow.org/images/colab_logo_32px.png\" />Run in Google Colab</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a target=\"_blank\" href=\"https://github.com/quantumlib/ReCirq/blob/master/docs/qaoa/routing_with_tket.ipynb\"><img src=\"https://www.tensorflow.org/images/GitHub-Mark-32px.png\" />View source on GitHub</a>\n",
        "  </td>\n",
        "  <td>\n",
        "    <a href=\"https://storage.googleapis.com/tensorflow_docs/ReCirq/docs/qaoa/routing_with_tket.ipynb\"><img src=\"https://www.tensorflow.org/images/download_logo_32px.png\" />Download notebook</a>\n",
        "  </td>\n",
        "</table>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-S_-zwQ5Lzhf"
      },
      "source": [
        "Wrap tket's compilation unit framework to keep track of qubit mappings and work with generic devices."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "czrY4tYHNBRO"
      },
      "source": [
        "## Setup\n",
        "\n",
        "Install the ReCirq package:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "8cBvm5NrNCXt"
      },
      "outputs": [],
      "source": [
        "try:\n",
        "    import recirq\n",
        "except ImportError:\n",
        "    !pip install git+https://github.com/quantumlib/ReCirq"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rNrxric3NKqM"
      },
      "source": [
        "Now import Cirq, ReCirq and the module dependencies:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "jwfyjjUxLzhj"
      },
      "outputs": [],
      "source": [
        "import cirq\n",
        "import recirq\n",
        "import networkx as nx\n",
        "from cirq.contrib.svg import SVGCircuit\n",
        "import numpy as np"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "6Z1Ub6hRLzhq"
      },
      "outputs": [],
      "source": [
        "from pytket.predicates import CompilationUnit, ConnectivityPredicate\n",
        "from pytket.passes import SequencePass, RoutingPass, DecomposeSwapsToCXs\n",
        "from pytket.routing import GraphPlacement"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7aFT1aKpLzhu"
      },
      "source": [
        "### Example circuit\n",
        "We'll route a 3-regular circuit to Sycamore23. To try to clear up some of the confusion about which indices are which, we'll construct the initial circuit with `LineQubits` 10 through 19 which should be thought of as \"logical indices\"."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "2ZkI9QFyLzhv"
      },
      "outputs": [],
      "source": [
        "from recirq.qaoa.problem_circuits import get_generic_qaoa_circuit\n",
        "from recirq.qaoa.gates_and_compilation import compile_problem_unitary_to_arbitrary_zz, \\\n",
        "    compile_driver_unitary_to_rx\n",
        "\n",
        "problem_graph = nx.random_regular_graph(d=3, n=10)\n",
        "nx.set_edge_attributes(problem_graph, values=1, name='weight')\n",
        "circuit_qubits = cirq.LineQubit.range(10, 20)\n",
        "gammas = np.random.randn(2)\n",
        "betas = np.random.randn(2)\n",
        "circuit = get_generic_qaoa_circuit(\n",
        "    problem_graph=problem_graph,\n",
        "    qubits=circuit_qubits,\n",
        "    gammas=gammas,\n",
        "    betas=betas)\n",
        "circuit = compile_problem_unitary_to_arbitrary_zz(circuit)\n",
        "circuit = compile_driver_unitary_to_rx(circuit)\n",
        "SVGCircuit(circuit)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZwSWNgqkLzh0"
      },
      "source": [
        "### \"Route\" this circuit\n",
        "\n",
        "Let's look at the \"connectivity graph\" of the circuit vs. that of the device"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "d6hnsXA0Lzh1"
      },
      "outputs": [],
      "source": [
        "import cirq.contrib.routing as ccr\n",
        "\n",
        "uncompiled_c_graph = ccr.get_circuit_connectivity(circuit)\n",
        "nx.draw_networkx(uncompiled_c_graph)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "YwtLw63mLzh4"
      },
      "outputs": [],
      "source": [
        "import cirq.google as cg\n",
        "\n",
        "dev_graph = ccr.xmon_device_to_graph(cg.Sycamore23)\n",
        "nx.draw_networkx(dev_graph)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "wSLdPQmwLzh8"
      },
      "outputs": [],
      "source": [
        "# alias for the device. If this notebook were wrapped\n",
        "# in a function, `circuit` and `device` would be the arguments\n",
        "device = cg.Sycamore23"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UZMHX0TfLzh_"
      },
      "source": [
        "### Mapping to device *indices*\n",
        "We'll keep a set of secret indices that number device qubits contiguously from zero instead of `(row, col)`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "qWak5p0QLziB"
      },
      "outputs": [],
      "source": [
        "index_to_qubit = sorted(device.qubit_set())\n",
        "qubit_to_index = {q: i for i, q in enumerate(index_to_qubit)}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G79yrP3_LziE"
      },
      "source": [
        "### Convert to pytket `Device`\n",
        "The provided function doesn't work with `SerializableDevice`. We use existing functionality to turn Devices into graphs to provide a more robust solution."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "2E-W4pJBLziF"
      },
      "outputs": [],
      "source": [
        "import pytket\n",
        "from pytket.circuit import Node\n",
        "\n",
        "def _qubit_index_edges():\n",
        "    dev_graph = ccr.xmon_device_to_graph(device)\n",
        "    for n1, n2 in dev_graph.edges:\n",
        "        #yield Node('q', n1.row, n1.col), Node('q', n2.row, n2.col)\n",
        "        yield (qubit_to_index[n1], qubit_to_index[n2])\n",
        "\n",
        "def _device_to_tket_device():\n",
        "    arc = pytket.routing.Architecture(\n",
        "        list(_qubit_index_edges())\n",
        "    )\n",
        "    return pytket.device.Device({}, {}, arc)\n",
        "\n",
        "tk_circuit = pytket.cirq.cirq_to_tk(circuit)\n",
        "tk_device = _device_to_tket_device()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "saC90prWLziI"
      },
      "source": [
        "### tket understands LineQubit and uses our strange indexing convention"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "jz5Km8QzLziJ"
      },
      "outputs": [],
      "source": [
        "tk_circuit.qubits"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9f_kDTkXLziM"
      },
      "source": [
        "### However, our device uses our secret indices\n",
        "\n",
        "There seems to be a bug if you use their built-in support for two-index qubits (nodes): `Existing register q cannot support id: q[6, 1]`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "igPQlOO9LziN"
      },
      "outputs": [],
      "source": [
        "tk_device.coupling"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ci-ctyWgLziR"
      },
      "source": [
        "### Placement and routing pass"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "XFqDGhq5LziR"
      },
      "outputs": [],
      "source": [
        "from pytket.predicates import CompilationUnit, ConnectivityPredicate\n",
        "from pytket.passes import SequencePass, RoutingPass, DecomposeSwapsToCXs, PlacementPass\n",
        "from pytket.routing import GraphPlacement"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "Rws7DjwQLziU"
      },
      "outputs": [],
      "source": [
        "unit = CompilationUnit(tk_circuit, [ConnectivityPredicate(tk_device)])\n",
        "passes = SequencePass([\n",
        "    PlacementPass(GraphPlacement(tk_device)),\n",
        "    RoutingPass(tk_device)])\n",
        "passes.apply(unit)\n",
        "valid = unit.check_all_predicates()\n",
        "assert valid"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IGw2STFBLziX"
      },
      "source": [
        "### The initial mapping\n",
        "This maps from logical LineQubits to secret device indices"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "bKh-ZXE-LziY"
      },
      "outputs": [],
      "source": [
        "unit.initial_map"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nfuiEUtZLzia"
      },
      "source": [
        "### Bookkept initial mapping\n",
        "We \"decode\" our tket conventions back into Cirq idioms."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "GguVHRklLzib"
      },
      "outputs": [],
      "source": [
        "def tk_to_i(tk):\n",
        "    i = tk.index\n",
        "    assert len(i) == 1, i\n",
        "    return i[0]\n",
        "\n",
        "initial_map = {cirq.LineQubit(tk_to_i(n1)): index_to_qubit[tk_to_i(n2)] for n1, n2 in unit.initial_map.items()}\n",
        "initial_map"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YPeQtWPOLzie"
      },
      "source": [
        "### The final mapping\n",
        "This maps from logical LineQubits to final secret device indices."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "TMe1ZunmLzif"
      },
      "outputs": [],
      "source": [
        "unit.final_map"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "utRI3lcBLzii"
      },
      "outputs": [],
      "source": [
        "final_map = {cirq.LineQubit(tk_to_i(n1)): index_to_qubit[tk_to_i(n2)]\n",
        "             for n1, n2 in unit.final_map.items()}\n",
        "final_map"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4wGb_vbYLzim"
      },
      "source": [
        "### The compilation unit applies the mapping\n",
        "So our circuit qubits use secret device indices"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "VYFQpNXsLzim"
      },
      "outputs": [],
      "source": [
        "unit.circuit.qubits"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JTAFgW8uLzip"
      },
      "source": [
        "### Map the circuit to grid qubits"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "0nIM0-VaLziq"
      },
      "outputs": [],
      "source": [
        "routed_circuit = pytket.cirq.tk_to_cirq(unit.circuit)\n",
        "routed_circuit = routed_circuit.transform_qubits(lambda q: index_to_qubit[q.x])\n",
        "SVGCircuit(routed_circuit)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "afZSGet3Lzit"
      },
      "source": [
        "### Now it's nice and compiled"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "wsT08hz4Lziu"
      },
      "outputs": [],
      "source": [
        "routed_c_graph = ccr.get_circuit_connectivity(routed_circuit)\n",
        "nx.draw_networkx(routed_c_graph)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XoWLNcPELzi5"
      },
      "source": [
        "### Check that circuits are equivalent"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "gElylkOxLzi5"
      },
      "outputs": [],
      "source": [
        "for _, op, _ in routed_circuit.findall_operations_with_gate_type(cirq.TwoQubitGate):\n",
        "    a, b = op.qubits\n",
        "    assert a.is_adjacent(b)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "QXULkstkLzi8"
      },
      "outputs": [],
      "source": [
        "import cirq.contrib.acquaintance as cca\n",
        "def permute_gate(qubits, permutation):\n",
        "    return cca.LinearPermutationGate(\n",
        "        num_qubits=len(qubits),\n",
        "        permutation={i: permutation[i] for i in range(len(permutation))}\n",
        "    ).on(*qubits)\n",
        "\n",
        "final_to_initial_map = {final_map[cq]: initial_map[cq]\n",
        "                              for cq in circuit_qubits}\n",
        "initial_qubits = [initial_map[cq] for cq in circuit_qubits]\n",
        "final_permutation = [initial_qubits.index(final_to_initial_map[q])\n",
        "                     for q in initial_qubits]\n",
        "rcircuit_with_perm = routed_circuit.copy()\n",
        "rcircuit_with_perm.append(permute_gate(initial_qubits, final_permutation))\n",
        "expected = circuit.unitary(qubit_order=cirq.QubitOrder.explicit(circuit_qubits))\n",
        "actual = rcircuit_with_perm.unitary(qubit_order=cirq.QubitOrder.explicit(initial_qubits))\n",
        "cirq.testing.assert_allclose_up_to_global_phase(expected, actual, atol=1e-8)"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "name": "routing_with_tket.ipynb",
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
